// @algorithm @lc id=233 lang=cpp 
// @title number-of-digit-one


// #define print(...)
// @test(13)=6
// @test(0)=0
class Solution {
public:
    int countDigitOne(int n) {
        int ans = 0;
        int64_t power = 1;
        for(int i=0; power<=n; i++){
            ans += n/(power*10)*power
                + min(power, max((int64_t)0, n%(power*10)-power+1));
            power *= 10;
        }
        return ans;
    }
};